package com.zs.letcode.binary_search;

/**
 * 有效的完全平方数
 * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
 * <p>
 * 进阶：不要 使用任何内置的库函数，如 sqrt 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：num = 16
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：num = 14
 * 输出：false
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= num <= 2^31 - 1
 * 相关标签
 * 数学
 * 二分查找
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xel3tc/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/7/31 09:34
 */
public class Chapter12 {
    public static void main(String[] args) {

    }

    private class Solution {
        /**
         * 方法一：二分查找
         *
         * @param num
         * @return
         */
        public boolean isPerfectSquare(int num) {
            if (num < 2) {
                return true;
            }
            long left = 2, right = num / 2, x, guessSquared;
            while (left <= right) {
                x = left + (right - left) / 2;
                guessSquared = x * x;
                if (guessSquared == num) {
                    return true;
                }
                if (guessSquared > num) {
                    right = x - 1;
                } else {
                    left = x + 1;
                }
            }
            return false;
        }

        /**
         * 方法二：牛顿迭代法
         */
        public boolean isPerfectSquare1(int num) {
            if (num < 2) {
                return true;
            }
            long x = num / 2;
            while (x * x > num) {
                x = (x + num / 2) / 2;
            }
            return (x * x == num);
        }
    }
}
